순환 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 성질
4. 유향 순환 그래프
- 4.1. 관련 개념
참조

1. 개요

순환 그래프는 n개의 꼭짓점과 꼭짓점 $v_i$와 $v_j$ 사이에 $i-j$가 1 또는 $n-1$일 때 변이 존재하는 그래프이다. 순환 그래프는 연결 평면 그래프이며, n이 짝수일 경우 이분 그래프이다. 순환 그래프의 색칠수는 꼭짓점 개수에 따라 다르며, 대칭군은 이면체군이다. 유향 순환 그래프는 방향이 있는 순환 그래프이며, 순환군의 케일리 그래프이다.

더 읽어볼만한 페이지

정규 그래프 - 페일리 그래프
페일리 그래프는 유한체와 제곱수를 기반으로 구성되며, 강하게 정규적이고 자기 여 그래프이며 해밀턴 순환 그래프이다.
정규 그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.
그래프 - 매케이 화살집
매케이 화살집은 유한군 G의 기약 표현을 꼭짓점으로, 텐서곱 분해를 통해 변을 정의하여 군의 표현론적 구조를 시각적으로 나타내는 도구이다.
그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.

순환 그래프
그래프 정보
순환 그래프 C5
자기 동형군	}} (})
색칠수	이 홀수일 경우 3, 그 외에는 2
색칠 지수	이 홀수일 경우 3, 그 외에는 2
표기법	}}
속성	2-정규 정점-추이 변-추이 단위 거리 해밀턴 오일러

2. 정의

크기가 $n$ 인 '''순환 그래프''' $C_n$ 은 $n$ 개의 꼭짓점 $V(C_n)=\{v_1,\dots,v_n\}$ 으로 구성된 (단순 무향) 그래프이며, 그 변은 다음과 같다.

: $v_iv_j\in E(C_n)\iff i\equiv j\pm1\pmod n$

순환 그래프는 '''단순 순환 그래프''', '''사이클''', '''다각형''', '''''n''-각형'''등으로 불리기도 한다. '''환상 그래프'''라고도 불리나, 비환상 그래프가 아닌 그래프 전반을 가리키는 경우도 있어 자주 사용되지는 않는다.^[3] '''''n''-사이클'''이라는 용어는 다른 상황에서 사용되기도 한다.

꼭짓점이 짝수 개인 사이클을 '''짝수 사이클''', 홀수 개인 사이클을 '''홀수 사이클'''이라고 한다.

3. 성질

순환 그래프는 다음과 같은 특징을 갖는다.

연결 그래프이다.
$n>2$ 인 경우 2-정규 그래프이다.
오일러 그래프이다.
해밀턴 그래프이다.
단위 거리 그래프이다.
대칭 그래프이다.
2-변 채색 가능 그래프이며, 정점의 수가 짝수일 때만 해당한다.
2-정점 채색 가능 그래프이며, 정점의 수가 짝수일 때만 해당한다. 더 일반적으로, 그래프가 이분 그래프가 되려면 홀수 사이클이 없어야 한다. (쾨니그, 1936).^[1]
선 그래프는 스스로와 동형이다.

:

L(C_n)\cong C_n

크기가 3 이하인 순환 그래프는 완전 그래프이다.

:

C_n\cong K_n\qquad(n=0,1,2,3)

크기가 4인 순환 그래프는 완전 이분 그래프이다.

:

C_4\cong K_{2,2}

순환 그래프는 정다각형으로 그릴 수 있으므로, ''n''-순환 그래프의 대칭성은 차수가 2''n''인 이면체군인 ''n''변의 정다각형의 대칭성과 동일하다.
하나의 닫힌 트레일을 가지며, 이는 순환 그래프 전체이다.
플라톤 그래프와 유사하게, 순환 그래프는 이각기둥의 골격을 형성한다. 이들의 쌍대 그래프는 쌍극자 그래프이며, 이는 호소헤드론의 골격을 형성한다.

순환 그래프

C_n

의 색칠수는 다음과 같다.

:

\chi(C_n)=\chi(L(C_n))=\begin{cases}n&n\le1\\2&n\ge2\land 2\mid n\\3&n\ge2\land 2\nmid n\end{cases}

4. 유향 순환 그래프

유향 순환 그래프(또는 방향 순환 그래프)는 모든 간선이 같은 방향을 향하고 있는 방향이 있는 순환 그래프이다.

유향 순환 그래프는 모든 변의 방향이 동일한 사이클 그래프의 유향 버전이다. 유향 순환 그래프의 각 정점은 입차수와 출차수가 모두 1이다.

사이클이 없는 유향 그래프는 유향 비순환 그래프라고 한다.

4. 1. 관련 개념

방향 그래프에서 각 유향 순환으로부터 적어도 하나의 간선을 포함하는 간선의 집합은 피드백 아크 집합이라고 한다. 이와 비슷하게 각 유향 순환으로부터 적어도 하나의 정점을 포함하는 정점의 집합은 피드백 버텍스 집합이라고 한다.

순환군의 경우 유향 순환 그래프는 케일리 그래프이다.

참조

_[1] PDF Some simple graph spectra http://www.win.tue.n[...]
_[2] 기타
_[3] 논문 Problem 11707 2013-05

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com